8595. Собаки и обезьяны

У Барыша есть n собак и m обезьян. Он хочет выстроить их в одну линию. Но он не хочет, чтобы в каком-либо месте стояло подряд две собаки или две обезьяны, потому что в таком случае они начинают драться. Сколько существует различных вариантов построения, таких чтобы ни обезьяны, ни собаки не дрались. Ответ выведите по модулю 10⁹ + 7. Имейте в виду, что собаки и обезьяны между собой различаются.

Вход. Два числа n и m (1 ≤ n, m ≤ 10⁵).

Выход. Выведите количество различных вариантов построения обезьян и собак по модулю 10⁹ + 7.

Пример входа 1	Пример выхода 1
2 2	8
Пример входа 2	Пример выхода 2
3 2	12
Пример входа 3	Пример выхода 3
1 8	0

РЕШЕНИЕ

комбинаторика

Анализ алгоритма

Если m > n + 1 или m < n – 1, то требуемой расстановки не существует, ответ 0. Если m = n, то собак и обезьян следует расположить чередуя друг с другом. Например, на четных местах можно поставить собак (n! вариантов, так как все собаки различные), на нечетных – обезьян (m! вариантов, обезьяны различные).

Аналогично можно на нечетных местах поставить собак, а на четных обезьян. Итого при m = n имеем 2 * n! * m! вариантов.

Если собак на 1 больше обезьян (или соответственно обезьян на 1 больше чем собак), то количество вариантов их расположения равно n! * m!

Реализация алгоритма

Вычисления следует проводить по модулю MOD = 10⁹ + 7.

#define MOD 1000000007

Функция fact вычисляет факториал n!

long long fact(int n)

{

long long res = 1;

for (int i = 2; i <= n; i++)

res = (res * i) % MOD;

return res;

}

Читаем входные данные.

scanf("%d %d", &m, &n);

Если собак на 2 больше чем обезьян или обезьян на 2 больше чем собак, то такая расстановка невозможна.

if (m > n + 1 || m < n - 1)

res = 0;

Если собак и обезьян одинаковое количество.

else if (m == n)

res = (fact(n) * fact(n) * 2) % MOD;

else

Если собак на 1 больше чем обезьян или обезьян на 1 больше чем собак.

res = (fact(n) * fact(m)) % MOD;

Выводим ответ.

printf("%lld\n", res);